package LeetcodeTest_nine;

import java.util.Scanner;

public class oddEvenList
{
    public static void main(String[] args)
    {
        ListNodes root=null;
        root=solution.createListNodes();
        root=solution.oddEvenList(root);
        solution.PrintNodes(root);
    }
}
class solution
{
    public static ListNodes oddEvenList(ListNodes head)
    {
        int count=0;
        ListNodes p0,p1,p2,curr;
        p0=p1=p2=curr=null;
        p0=p1=head;
        if(head==null||head.next==null)
            return head;
        curr=p1.next;
        if(curr.next==null)
            return head;
        else
        {
            p1=p0.next;
            curr=p1.next;
            count=2;
            if(curr.next!=null)
                p2=curr.next;
            while(curr.next!=null)
            {
                if(count%2==0)
                {
                    ListNodes p = new ListNodes(curr.val);
                    p1.next = p2;
                    p.next = p0.next;
                    p0.next = p;
                    p0 = p0.next;
                }
                else
                    p1=p1.next;
                curr = p2;
                p2 = p2.next;
                count++;
            }
            if(count%2==0)
            {
                ListNodes p=new ListNodes(curr.val);
                p1.next=null;
                p.next=p0.next;
                p0.next=p;
            }
        }
        return head;
    }
    public static ListNodes createListNodes()
    {
        Scanner reader=new Scanner(System.in);
        ListNodes head=null;
        ListNodes tail=null;
        head=new ListNodes(1);
        tail=head;
        for(int i=0;i<5;i++)
        {
            ListNodes p=new ListNodes(reader.nextInt());
            tail.next=p;
            tail=tail.next;
        }
        return head;
    }
    public static void PrintNodes(ListNodes p)
    {
        while(p!=null)
        {
            System.out.print(p.val+" ");
            p=p.next;
        }
    }
}
class ListNodes
{
    int val;
    ListNodes next;
    ListNodes() { }
    ListNodes(int val)
    {
        this.val = val;
    }
    ListNodes(int val, ListNodes next)
    {
        this.val = val;
        this.next = next;
    }
}